In the field of computing systems there is often the need to share access to a resource between multiple agents. An agent needing access to a resource may be referred to as a “requester” for the resource. When there is more than one requester requesting access to a resource, a selection must be made to determine which requester is currently allowed access the resource. Therefore, arbitration for a resource is generally the selection of agents to be allowed access to the resource. For example, there may be several agents needing to perform a transaction requiring access to the resource of a shared computer bus. Arbitration for the computer bus is the selection of the agent that is allowed to issue the next transaction request onto the computer bus.
Arbitration schemes generally attempt to provide some level of fairness in the allocation of resources. However, many prior arbitration schemes are vulnerable to arbitration problems such as “lock out” and/or “deadlock.” More particularly, a competing interest in arbitration schemes is the fact that some requests for a resource may be of a higher priority than others, yet lock out or deadlock may be an undesirable byproduct of placing a heavy emphasis on higher priority requests. For example, if one or more agents can monopolize access to the resource, then the remaining agents may be “locked out” from accessing the resource. Lock out of any agent may cause the computing system to cease making progress on some of the computations being performed by the computing system. Lock out may also cause the entire computing system to cease making any progress at all, a condition denoted system “deadlock.” Lock out and especially deadlock must generally be avoided. Prior arbitration schemes are vulnerable to lock out and deadlock.
In prior art arbitration systems, it is often the case that an emphasis is placed on either a fairness to the requesters or deference to high priority requests. Systems placing an emphasis on fairness may not, however, adequately process higher priority requests. For example, a round robin arbitration scheme would grant access to a resource equally between low and high priority requests, which may be undesirable. On the other hand, complete deference to high priority requests may cause lock out and in some cases deadlock for lower priority requests, which may be equally undesirable.
Accordingly, there is a need in the computing systems industry for an improved arbitration scheme that addresses the aforementioned and other shortcomings of the prior art. The present invention fulfills these and other needs, and offers other advantages over prior art arbitration approaches.